package leetcode;

/**
 * 132. 分割回文串 II
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
 * 返回符合要求的 最少分割次数 。
 * 示例 1：
 * 输入：s = "aab"
 * 输出：1
 * 解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
 * 示例 2：
 * 输入：s = "a"
 * 输出：0
 * 示例 3：
 * 输入：s = "ab"
 * 输出：1
 * 提示：
 * 1 <= s.length <= 2000
 * s 仅由小写英文字母组成
 */

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class problems_132 {

    public static void main(String[] arge) {
        System.out.println(new Solution().minCut("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"));
    }

    static class Solution {
        /**
         * 官方算法
         * 设定dp，dp[i][j]，标识字符串s，i到j直接字符串是否是回文
         *      a   b   c   b   a
         *  a   √
         *  b   ×   √
         *  c   ×   ×   √
         *  b   ×   √   ×   √
         *  a   √   ×   ×   ×   √
         *
         *      a   b   c   b   e
         *  a   √
         *  b   ×   √
         *  c   ×   ×   √
         *  b   ×   √   ×   √
         *  e   ×   ×   ×   ×   √
         *
         *
         *      a   b   c   d   a
         *  a   √
         *  b   ×   √
         *  c   ×   ×   √
         *  d   ×   ×   ×   √
         *  a   ×   ×   ×   ×   √
         *
         * 观察总结，dp[i][j]为回文的条件是：s[i] == s[j] 并且其内部，即dp[i+1][j-1]为true，是回文
         * 然后，dp2为s字符串从0下标开始，最小分割数，dp2[0] = 0,dp2[n]=dp2[n-1] + 1,或者内部出现回文时，使用回文的dp2
         * (比如, abc，dp2为2，如果追加的是b，则可划分成[a,bcb]，也就是dp[1]=1，[a,b]，把b扩展成bcb的情况)
         */
        public int minCut(String s) {
            if (isHuiWen(s,0, s.length())){
                return 0;
            }

            int n = s.length();
            // 动态规划处理
            boolean[][] g = new boolean[n][n];
            for (int i = 0; i < n; ++i) {
                Arrays.fill(g[i], true);
            }

            for (int i = n - 1; i >= 0; --i) {
                for (int j = i + 1; j < n; ++j) {
                    g[i][j] = s.charAt(i) == s.charAt(j) && g[i + 1][j - 1];
                }
            }

            int[] f = new int[n];
            Arrays.fill(f, Integer.MAX_VALUE);
            for (int i = 0; i < n; ++i) {
                if (g[0][i]) {
                    f[i] = 0;
                } else {
                    for (int j = 0; j < i; ++j) {
                        if (g[j + 1][i]) {
                            f[i] = Math.min(f[i], f[j] + 1);
                        }
                    }
                }
            }

            return f[n - 1];
        }
        /**
         * 回文字符串判断
         */
        private boolean isHuiWen(String s, int i, int len) {
            if (i == len || Math.abs(len - i) <= 1) return true;
            int helf = Math.abs(len - i) / 2;
            for (int index = 0; index < helf; index++) {
                if (s.charAt(i + index) != s.charAt(len - 1 - index)) {
                    return false;
                }
            }
            return true;
        }
    }


    /**
     * 超时失败
     */
    // static class Solution {
    //     int min = Integer.MAX_VALUE;
    //
    //     public int minCut(String s) {
    //         if(null == s || s.length() == 0) return 0;
    //         // 初始化
    //         // 最多切割len-1次
    //         min = s.length() - 1;
    //
    //         Deque<String> deque = new ArrayDeque<>();
    //         backtracking(s, 0, s.length(), deque);
    //         return min;
    //     }
    //     /**
    //      * 判断文字
    //      * 判断的是正途的一部分
    //      */
    //     private void backtracking(String txt, int start, int len, Deque<String> deque) {
    //         // 如果指针已经指到最后，判断成功，返回
    //         if (start == len) {
    //             if (deque.size() - 1 < min) min = deque.size() - 1;
    //             return;
    //         }
    //         // 遍历对象
    //         for (int i = start; i < len; i++) {
    //             // 比较前半部分
    //             if (!isHuiWen(txt, start, i + 1)) {
    //                 continue;
    //             }
    //             // 前半是回文，则追加前半
    //             deque.add(txt.substring(start, i + 1));
    //             if (deque.size() - 1 < min) {
    //                 // 然后，
    //                 backtracking(txt, i + 1, len, deque);
    //             }
    //             deque.removeLast();
    //         }
    //     }
    //
    //     /**
    //      * 回文字符串判断
    //      */
    //     private boolean isHuiWen(String s, int i, int len) {
    //         if (i == len || Math.abs(len - i) <= 1) return true;
    //         int helf = Math.abs(len - i) / 2;
    //         for (int index = 0; index < helf; index++) {
    //             if (s.charAt(i + index) != s.charAt(len - 1 - index)) {
    //                 return false;
    //             }
    //         }
    //         return true;
    //     }
    // }
}
